﻿using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GraphImplementation
{

    public class NodeList<T> : Collection<Node<T>>
    {
        public NodeList() : base() { }

        public NodeList(int initialSize)
        {
            // Add the specified number of items
            for (int i = 0; i < initialSize; i++)
                base.Items.Add(default(Node<T>));
        }

        public Node<T> FindByValue(T value)
        {
            // search the list for the value
            foreach (Node<T> node in Items)
                if (node.Value.Equals(value))
                    return node;

            // if we reached here, we didn't find a matching node
            return null;
        }
        public bool inside(Node<T> compare)
        {
            foreach (var item in Items)
	        {
                if (item.Value.Equals(compare.Value))
                {
                    return true;
                }
	        }
            return false;
    
        }

       

        
    };

    public class Node<T>
    {
            // Private member-variables
            private T data;
            private NodeList<T> neighbors = null;

            public Node() {}
            public Node(T data) : this(data, null) {}
            public Node(T data, NodeList<T> neighbors)
            {
                this.data = data;
                this.neighbors = neighbors;
            }

            public T Value
            {
                get
                {
                    return data;
                }
                set
                {
                    data = value;
                }
            }

            protected NodeList<T> Neighbors
            {
                get
                {
                    return neighbors;
                }
                set
                {
                    neighbors = value;
                }
            }

            public override string ToString()
            {
                return this.data.ToString();
            }
        };


    public class GraphNode<T> : Node<T>
    {
        private List<int> costs;

        public GraphNode() : base() { }
        public GraphNode(T value) : base(value) { }
        public GraphNode(T value, NodeList<T> neighbors) : base(value, neighbors) { }

        new public NodeList<T> Neighbors
        {
            get
            {
                if (base.Neighbors == null)
                    base.Neighbors = new NodeList<T>();

                return base.Neighbors;
            }
        }

        public List<int> Costs
        {
            get
            {
                if (costs == null)
                    costs = new List<int>();

                return costs;
            }
        }
    };

    public class Graph<T> 
    {
        private NodeList<T> nodeSet;


        public Graph() : this(null) { }
        public Graph(NodeList<T> nodeSet)
        {
            if (nodeSet == null)
                this.nodeSet = new NodeList<T>();
            else
                this.nodeSet = nodeSet;
        }

        public void AddNode(GraphNode<T> node)
        {
            // adds a node to the graph
            nodeSet.Add(node);
        }

        public void AddNode(T value)
        {
            // adds a node to the graph
            nodeSet.Add(new GraphNode<T>(value));
        }

        public void AddDirectedEdge(GraphNode<T> from, GraphNode<T> to, int cost)
        {
            from.Neighbors.Add(to);
            from.Costs.Add(cost);
        }

        public void AddUndirectedEdge(T from, T to, int cost)
        {
            GraphNode<T> a = this.find(from);
            GraphNode<T> b = this.find(to);
            this.AddUndirectedEdge(a, b, cost);
        }
        private GraphNode<T> find(T searchValue)
        {
            GraphNode<T> node =(GraphNode<T>) nodeSet.FindByValue(searchValue);
            return node;
        }
        public void AddUndirectedEdge(GraphNode<T> from, GraphNode<T> to, int cost)
        {
            from.Neighbors.Add(to);
            from.Costs.Add(cost);

            to.Neighbors.Add(from);
            to.Costs.Add(cost);
        }

        

        public bool Remove(T value)
        {
            // first remove the node from the nodeset
            GraphNode<T> nodeToRemove = (GraphNode<T>)nodeSet.FindByValue(value);
            if (nodeToRemove == null)
                // node wasn't found
                return false;

            // otherwise, the node was found
            nodeSet.Remove(nodeToRemove);

            // enumerate through each node in the nodeSet, removing edges to this node
            foreach (GraphNode<T> gnode in nodeSet)
            {
                int index = gnode.Neighbors.IndexOf(nodeToRemove);
                if (index != -1)
                {
                    // remove the reference to the node and associated cost
                    gnode.Neighbors.RemoveAt(index);
                    gnode.Costs.RemoveAt(index);
                }
            }

            return true;
        }

        public NodeList<T> Nodes
        {
            get
            {
                return nodeSet;
            }
        }

        public int Count
        {
            get { return nodeSet.Count; }
        }
    };

    class Edge<T> : IComparable<Edge<T>>
    {
        public Node<T> firstNode;
        public Node<T> secondNode;
        public int cost;

       public Edge(Node<T> firstNode, Node<T> secondNode, int cost)
        {
            this.firstNode = firstNode;
            this.secondNode = secondNode;
            this.cost = cost;
        }
       public int CompareTo(Edge<T> other)
       {
           if (this.cost > other.cost)
           {
               return 1;
           }
           else if (this.cost < other.cost)
           {
               return -1;
           }
           return 0;
       }

       public override string ToString()
       {
           string result = this.firstNode.ToString() +" "+ this.secondNode.ToString() + " " + this.cost;
           return result;
       }

    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph<int> web = new Graph<int>();
            

            string line;
            using (StreamReader reader = new StreamReader("nodes.txt"))
            {
                line = reader.ReadLine();
                string[] token = line.Split(' ');
                int numberOfNodes = int.Parse(token[0]);
                for (int index = 1; index <= numberOfNodes; index++)
                {
                    web.AddNode(index);
                }
                while ((line = reader.ReadLine()) != null) //pro4itame rebrata i gi slagame v grafa
                {
                    //list.Add(line); // Add to list.

                   // Console.WriteLine(line);

                    token = line.Split(' ');
                    int firstNode = int.Parse(token[0]);
                    int secondNode = int.Parse(token[1]);
                    int cost = int.Parse(token[2]);

                    web.AddUndirectedEdge(firstNode, secondNode, cost);
                }
            }



            //web.AddNode("Privacy.htm");
            //web.AddNode("People.aspx");
            //web.AddNode("About.htm");
            //web.AddNode("Index.htm");
            //web.AddNode("Products.aspx");
            //web.AddNode("Contact.aspx");
            //int a = 5;

            //web.AddUndirectedEdge("People.aspx", "Privacy.htm", a); // People -> Privacy
            //web.AddUndirectedEdge("People.aspx", "Contact.aspx", 6); // People -> Privacy
            //web.AddUndirectedEdge("People.aspx", "Index.htm", 7); // People -> Privacy

            //web.AddDirectedEdge(new GraphNode<string>("Privacy.htm"),new GraphNode<string>( "Index.htm"),2);    // Privacy -> Index
            //web.AddDirectedEdge(new GraphNode<string>("Privacy.htm"),new GraphNode<string>( "About.htm"),3);    // Privacy -> About


            NodeList<int> remainingNodesToAdd = web.Nodes;
            List<Edge<int>> edgesToBeChoosen = new List<Edge<int>>();



             GraphNode<int> d = (GraphNode<int>) remainingNodesToAdd.FindByValue(1);
             List<int> weight = d.Costs;
             NodeList<int> neighbours = d.Neighbors;


             for (int index = 0; index < neighbours.Count; index++)
             {
                 Edge<int> r = new Edge<int>(new Node<int>(1), neighbours[index], weight[index]);
                 edgesToBeChoosen.Add(r);

             }
             Edge<int> front = edgesToBeChoosen[0];
        
             int minimumSpaningTreeSum = 0;
            

            remainingNodesToAdd.Remove(remainingNodesToAdd.FindByValue(1));

            

            


            while (remainingNodesToAdd.Count != 0)
            {
               


                edgesToBeChoosen.Sort();
                
                Node<int> currentNode = new Node<int>();
                int index;
                for (index = 0; index < edgesToBeChoosen.Count; index++)
                {
                    if (remainingNodesToAdd.inside( edgesToBeChoosen[index].firstNode) || remainingNodesToAdd.inside( edgesToBeChoosen[index].secondNode) )
                    {
                        if (remainingNodesToAdd.inside( edgesToBeChoosen[index].firstNode))
                        {
                            for (int index1 = 0; index1 < neighbours.Count; index1++)
                            {
                                Edge<int> r = new Edge<int>(edgesToBeChoosen[index1].firstNode, neighbours[index1], weight[index1]);
                                edgesToBeChoosen.Add(r);
                            }
                            currentNode = edgesToBeChoosen[index].firstNode;
                            minimumSpaningTreeSum += edgesToBeChoosen[index].cost;
                            
                        }
                        else
                        {
                            for (int index1 = 0; index1 < neighbours.Count; index1++)
                            {
                                Edge<int> r = new Edge<int>(edgesToBeChoosen[index1].secondNode, neighbours[index1], weight[index1]);
                                edgesToBeChoosen.Add(r);
                            }
                            currentNode = edgesToBeChoosen[index].secondNode;
                            minimumSpaningTreeSum += edgesToBeChoosen[index].cost;
                        }
                        break;
                    }
                    edgesToBeChoosen.Remove(edgesToBeChoosen[index]);
                }

                //edgesToBeChoosen.Remove(edgesToBeChoosen[0]);
                Console.WriteLine(minimumSpaningTreeSum);
                remainingNodesToAdd.Remove(currentNode);
                Console.WriteLine(remainingNodesToAdd.Count);





                //for (int index = 0; index < neighbours.Count; index++)
                //{
                //    Edge<int> r = new Edge<int>(new Node<int>(1), neighbours[index], weight[index]);
                //    edgesToBeChoosen.Add(r);

                //}

            }


            Console.WriteLine(minimumSpaningTreeSum);
          
           //foreach (var item in weight)
           //{
           //    Console.WriteLine(item);
           //}
           //Console.WriteLine();
           //foreach (var item in neighbours)
           //{
           //    Console.WriteLine(item);
           //}






            //web.AddDirectedEdge("About.htm", "Privacy.htm");    // About -> Privacy
            //web.AddDirectedEdge("About.htm", "People.aspx");    // About -> People
            //web.AddDirectedEdge("About.htm", "Contact.aspx");   // About -> Contact

            //web.AddDirectedEdge("Index.htm", "About.htm");      // Index -> About
            //web.AddDirectedEdge("Index.htm", "Contact.aspx");   // Index -> Contacts
            //web.AddDirectedEdge("Index.htm", "Products.aspx");  // Index -> Products

            //web.AddDirectedEdge("Products.aspx", "Index.htm");  // Products -> Index
            //web.AddDirectedEdge("Products.aspx", "People.aspx");// Products -> People
        }
    }
}
